{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Tic-Tac-Toe State"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validTicTacToe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效的井字游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>board</code> 表示井字游戏的棋盘。当且仅当在井字游戏过程中，棋盘有可能达到 <code>board</code> 所显示的状态时，才返回 <code>true</code> 。</p>\n",
    "\n",
    "<p>井字游戏的棋盘是一个 <code>3 x 3</code> 数组，由字符 <code>' '</code>，<code>'X'</code> 和 <code>'O'</code> 组成。字符 <code>' '</code> 代表一个空位。</p>\n",
    "\n",
    "<p>以下是井字游戏的规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>玩家轮流将字符放入空位（<code>' '</code>）中。</li>\n",
    "\t<li>玩家 1 总是放字符 <code>'X'</code> ，而玩家 2 总是放字符 <code>'O'</code> 。</li>\n",
    "\t<li><code>'X'</code> 和 <code>'O'</code> 只允许放置在空位中，不允许对已放有字符的位置进行填充。</li>\n",
    "\t<li>当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束。</li>\n",
    "\t<li>当所有位置非空时，也算为游戏结束。</li>\n",
    "\t<li>如果游戏结束，玩家不允许再放置字符。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/15/tictactoe1-grid.jpg\" style=\"width: 253px; height: 253px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [\"O  \",\"   \",\"   \"]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>玩家 1 总是放字符 \"X\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/15/tictactoe2-grid.jpg\" style=\"width: 253px; height: 253px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [\"XOX\",\" X \",\"   \"]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>玩家应该轮流放字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/15/tictactoe4-grid.jpg\" style=\"width: 253px; height: 253px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [\"XOX\",\"O O\",\"XOX\"]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>board.length == 3</code></li>\n",
    "\t<li><code>board[i].length == 3</code></li>\n",
    "\t<li><code>board[i][j]</code> 为 <code>'X'</code>、<code>'O'</code> 或 <code>' '</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-tic-tac-toe-state](https://leetcode.cn/problems/valid-tic-tac-toe-state/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-tic-tac-toe-state](https://leetcode.cn/problems/valid-tic-tac-toe-state/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"O  \",\"   \",\"   \"]', '[\"XOX\",\" X \",\"   \"]', '[\"XOX\",\"O O\",\"XOX\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        # n = len(board)\n",
    "        n = 3\n",
    "        x_num = self.counter(board, \"X\")\n",
    "        o_num = self.counter(board, \"O\")\n",
    "\n",
    "        # 顺序不对\n",
    "        if o_num > x_num or x_num-o_num>1: return False\n",
    "        # x赢 或 o赢\n",
    "        res1 = self.winer(board, n, \"X\")\n",
    "        res2 = self.winer(board, n, \"O\")\n",
    "        if x_num == o_num and res1 == \"X\": return False\n",
    "        if x_num > o_num and res2 == \"O\": return False\n",
    "        # if res1 != -1 and res2 != -1: return False # 输出赢家\n",
    "\n",
    "        return True\n",
    "\n",
    "    # 统计各方棋子\n",
    "    def counter(self, board, x):\n",
    "        counts = 0 \n",
    "        for strs in board:\n",
    "            for s in strs:\n",
    "                if s == x:\n",
    "                    counts += 1 \n",
    "        return counts\n",
    "\n",
    "    # 判断谁赢得比赛\n",
    "    def winer(self, board, n, x):\n",
    "        slash1 = \"\"\n",
    "        slash2 = \"\"\n",
    "        for i in range(n):\n",
    "            # 第i行的三个元素\n",
    "            row = board[i]\n",
    "            # 第i列的三个元素\n",
    "            column = \"\"\n",
    "            for j in range(n):\n",
    "                column += board[j][i]\n",
    "            if row == x*n or column == x*n: return x\n",
    "            slash1 += board[i][i]\n",
    "            slash2 += board[i][n-i-1]\n",
    "        if slash1 == x*n or slash2 == x*n: return x\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        rowTag = [i[0] for i in board]\n",
    "        colTag = [i for i in board[0]]\n",
    "        leftTag = board[0][0]\n",
    "        rightTag = board[0][-1]\n",
    "        x = 0\n",
    "        for row in range(3):\n",
    "            for col in range(3):\n",
    "                cur = board[row][col]\n",
    "                if cur == 'X':\n",
    "                    x += 1\n",
    "                elif cur == 'O':\n",
    "                    x -= 1\n",
    "                if cur != rowTag[row]:\n",
    "                    rowTag[row] = 'n'\n",
    "                if cur != colTag[col]:\n",
    "                    colTag[col] = 'n'\n",
    "                if row == col and cur != leftTag:\n",
    "                    leftTag = 'n'\n",
    "                if row + col == 2 and cur != rightTag:\n",
    "                    rightTag = 'n'\n",
    "        y = 0\n",
    "        flag = False\n",
    "        for i, j in zip(rowTag, colTag):\n",
    "            if i == 'X':\n",
    "                flag = True\n",
    "                y += 1\n",
    "            elif i == 'O':\n",
    "                y -= 1\n",
    "            if j == 'X':\n",
    "                flag = True\n",
    "                y += 1\n",
    "            elif j == 'O':\n",
    "                y -= 1\n",
    "        if leftTag == 'X':\n",
    "            flag = True\n",
    "            y += 1\n",
    "        elif leftTag == 'O':\n",
    "            y -= 1\n",
    "        if rightTag == 'X':\n",
    "            flag = True\n",
    "            y += 1\n",
    "        elif rightTag == 'O':\n",
    "            y -= 1\n",
    "        if x == 1 and y > 0:\n",
    "            return True\n",
    "        if y == 0 and not flag and (x == 1 or x == 0):\n",
    "            return True\n",
    "        if y < 0 and x == 0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        n = len(board)\n",
    "        x_num = self.counter(board, \"X\")\n",
    "        o_num = self.counter(board, \"O\")\n",
    "\n",
    "        # 顺序不对\n",
    "        if o_num > x_num or x_num-o_num>1: return False\n",
    "        # x赢 或 o赢\n",
    "        res1 = self.winer(board, n, \"X\")\n",
    "        res2 = self.winer(board, n, \"O\")\n",
    "        if x_num == o_num and res1 == \"X\": return False\n",
    "        if x_num > o_num and res2 == \"O\": return False\n",
    "        if res1 != -1 and res2 != -1: return False # 输出赢家\n",
    "\n",
    "        return True\n",
    "\n",
    "    # 统计各方棋子\n",
    "    def counter(self, board, x):\n",
    "        counts = 0 \n",
    "        for strs in board:\n",
    "            for s in strs:\n",
    "                if s == x:\n",
    "                    counts += 1 \n",
    "        return counts\n",
    "\n",
    "    # 判断谁赢得比赛\n",
    "    def winer(self, board, n, x):\n",
    "        for i in range(n):\n",
    "            # 第i行的三个元素\n",
    "            row = board[i]\n",
    "            # 第i列的三个元素\n",
    "            column = \"\"\n",
    "            for j in range(n):\n",
    "                column += board[j][i]\n",
    "            if row == x*n or column == x*n: return x\n",
    "        slash1 = \"\"\n",
    "        slash2 = \"\"\n",
    "        for i in range(n):\n",
    "            slash1 += board[i][i]\n",
    "            slash2 += board[i][n-i-1]\n",
    "        if slash1 == x*n or slash2 == x*n: return x\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        chN = True\n",
    "        nums1, nums2 = 0, 0\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 'X':\n",
    "                    nums1 += 1\n",
    "                if board[i][j] == 'O':\n",
    "                    nums2 += 1\n",
    "        if nums1 < nums2 or nums1-nums2>=2:\n",
    "            chN = False\n",
    "        \n",
    "        chT = True\n",
    "        bingo1, bingo2 = 0, 0\n",
    "        for i in range(3):\n",
    "            if board[i][0] == board[i][1] and board[i][1] == board[i][2]:\n",
    "                if board[i][0] == 'X':\n",
    "                    bingo1 += 1\n",
    "                if board[i][0] == 'O':\n",
    "                    bingo2 += 1\n",
    "            if board[0][i] == board[1][i] and board[1][i] == board[2][i]:\n",
    "                if board[0][i] == 'X':\n",
    "                    bingo1 += 1\n",
    "                if board[0][i] == 'O':\n",
    "                    bingo2 += 1\n",
    "        if board[0][0] == board[1][1] and board[1][1] == board[2][2]:\n",
    "            if board[0][0] == 'X':\n",
    "                bingo1 += 1\n",
    "            if board[0][0] == 'O':\n",
    "                bingo2 += 1\n",
    "        if board[2][0] == board[1][1] and board[1][1] == board[0][2]:\n",
    "            if board[2][0] == 'X':\n",
    "                bingo1 += 1\n",
    "            if board[2][0] == 'O':\n",
    "                bingo2 += 1\n",
    "        \n",
    "        if bingo1 + bingo2 > 2:\n",
    "            chT = False\n",
    "        if bingo1 == bingo2 and bingo1!=0:\n",
    "            chT = False\n",
    "\n",
    "        if chN and chT:\n",
    "            if (bingo1 == 1 and nums1 == nums2) or (bingo2 == 1 and nums1 == nums2+1):\n",
    "                return False       \n",
    "            return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[0][2] == p and board[1][1] == p and board[2][0] == p\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        # n = len(board)\n",
    "        n = 3\n",
    "        x_num = self.counter(board, \"X\")\n",
    "        o_num = self.counter(board, \"O\")\n",
    "\n",
    "        # 顺序不对\n",
    "        if o_num > x_num or x_num-o_num>1: return False\n",
    "        # x赢 或 o赢\n",
    "        res1 = self.winer(board, n, \"X\")\n",
    "        res2 = self.winer(board, n, \"O\")\n",
    "        if x_num == o_num and res1 == \"X\": return False\n",
    "        if x_num > o_num and res2 == \"O\": return False\n",
    "        if res1 != -1 and res2 != -1: return False # 输出赢家\n",
    "\n",
    "        return True\n",
    "\n",
    "    # 统计各方棋子\n",
    "    def counter(self, board, x):\n",
    "        counts = 0 \n",
    "        for strs in board:\n",
    "            for s in strs:\n",
    "                if s == x:\n",
    "                    counts += 1 \n",
    "        return counts\n",
    "\n",
    "    # 判断谁赢得比赛\n",
    "    def winer(self, board, n, x):\n",
    "        slash1 = \"\"\n",
    "        slash2 = \"\"\n",
    "        for i in range(n):\n",
    "            # 第i行的三个元素\n",
    "            row = board[i]\n",
    "            # 第i列的三个元素\n",
    "            column = \"\"\n",
    "            for j in range(n):\n",
    "                column += board[j][i]\n",
    "            if row == x*n or column == x*n: return x\n",
    "            slash1 += board[i][i]\n",
    "            slash2 += board[i][n-i-1]\n",
    "        if slash1 == x*n or slash2 == x*n: return x\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        cnto = 0\n",
    "        cntx = 0\n",
    "        for i in board:\n",
    "            for j in i:\n",
    "                if j == 'O':\n",
    "                    cnto += 1\n",
    "                elif j == 'X':\n",
    "                    cntx += 1\n",
    "        # print(cnto)\n",
    "        # print(cntx)\n",
    "        if cnto > cntx or cntx > cnto + 1:\n",
    "            return False \n",
    "        def iscomplete(s):\n",
    "            for i in board:\n",
    "                if all(j == s for j in i):\n",
    "                    return True \n",
    "            for i in range(3):\n",
    "                col = []\n",
    "                for j in range(3):\n",
    "                    col.append(board[j][i])\n",
    "                if all(w == s for w in col):\n",
    "                    return True \n",
    "            if board[0][0] == board[1][1] == board[2][2] == s:\n",
    "                return True \n",
    "            if board[0][2] == board[1][1] == board[2][0] == s:\n",
    "                return True\n",
    "            return False\n",
    "        if iscomplete('O') and iscomplete('X'):\n",
    "            return False\n",
    "        if iscomplete('X') and cntx <= cnto:\n",
    "            return False\n",
    "        if iscomplete('O') and cntx > cnto:\n",
    "            return False\n",
    "\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[0][2] == p and board[1][1] == p and board[2][0] == p\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        mat = [[0]*3 for i in range(3)]\n",
    "        dic = {' ':0,'X':1,'O':-1}\n",
    "        cnt_all = 0\n",
    "        p = 0\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                mat[i][j] = dic[board[i][j]]\n",
    "                cnt_all += dic[board[i][j]]\n",
    "                p += abs(dic[board[i][j]])\n",
    "        if (cnt_all == 0 or cnt_all == 1) :\n",
    "            h = [0] *3\n",
    "            v = [0] *3\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    h[i] += mat[i][j]\n",
    "                    v[j] += mat[i][j]\n",
    "            a = 0\n",
    "            b = 0\n",
    "            for i in range(3):\n",
    "                a +=mat[i][i]\n",
    "                b +=mat[i][2-i]\n",
    "            aa = False\n",
    "            bb = False\n",
    "            if 3 in h or 3 in v or a==3 or b ==3:\n",
    "                aa = True\n",
    "            if -3 in h or -3 in v or a==-3 or b ==-3:\n",
    "                bb = True\n",
    "\n",
    "            if aa and bb:\n",
    "                return False\n",
    "            elif aa and mod(p,2) == 0:\n",
    "                return False\n",
    "            elif bb and mod(p,2) == 1:\n",
    "                return False \n",
    "\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        \n",
    "        \"\"\" \n",
    "        1. `X` 的数量总是等于`O`的数量或者比它多1 （保证先手顺序）\n",
    "        2. 只能有一个胜者，或者没有胜者而棋盘是满的\n",
    "        3. `X`获胜时，`X`的棋子数量比`O`多1，且`O`未获胜\n",
    "        4. `O`获胜时，`O`的棋子数量和`X`相同，且`X`未获胜\n",
    "        \"\"\"\n",
    "        \n",
    "        xNum = sum([ sum([x == 'X' for x in line]) for line in board])\n",
    "        oNum = sum([ sum([x == 'O' for x in line]) for line in board])\n",
    "        \n",
    "        if (xNum != oNum) and (xNum - oNum != 1):\n",
    "            return False\n",
    "        \n",
    "        # 这一段来自checkIO上x-o-referee最简洁的解法\n",
    "        cols = map(''.join, zip(*board))\n",
    "        diag = map(''.join, zip(*[(r[i],r[2-i]) for i,r in enumerate(board) ]))\n",
    "        lines = board + list(cols) + list(diag)\n",
    "        \n",
    "        oWin = True if 'OOO' in lines else False\n",
    "        xWin = True if 'XXX' in lines else False\n",
    "        \n",
    "        if oWin and xWin:\n",
    "            return False\n",
    "        \n",
    "        if oWin and (xNum != oNum):\n",
    "            return False\n",
    "        \n",
    "        if xWin and (xNum - oNum != 1):\n",
    "            return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x_count = sum(row.count(\"X\") for row in board)\n",
    "        o_count = sum(row.count(\"O\") for row in board)\n",
    "        if o_count not in {x_count - 1, x_count}:\n",
    "            return False\n",
    "        if self.win(board, \"X\") and x_count - 1 != o_count:\n",
    "            return False\n",
    "        if self.win(board, \"O\") and x_count != o_count:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def win(self, board: List[str], player: str) -> bool:\n",
    "        for i in range(3):\n",
    "            if all(board[i][j] == player for j in range(3)):\n",
    "                return True\n",
    "            if all(board[j][i] == player for j in range(3)):\n",
    "                return True\n",
    "        if board[1][1] == player:\n",
    "            if board[0][0] == board[2][2] == player:\n",
    "                return True\n",
    "            if board[0][2] == board[2][0] == player:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[0][2] == p and board[1][1] == p and board[2][0] == p\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[0][2] == p and board[1][1] == p and board[2][0] == p\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        m = defaultdict(int)  # 记录'X'与'O'的次数\n",
    "        for line in board:\n",
    "            for c in line:\n",
    "                m[c] += 1\n",
    "        \n",
    "        # 返回s是否赢了\n",
    "        def check(s:str):\n",
    "            # 检查行\n",
    "            for r in range(3):\n",
    "                if board[r] == s * 3:\n",
    "                    return True\n",
    "            # 检查列\n",
    "            for c in range(3):\n",
    "                col = ''.join([x[c] for x in board])\n",
    "                if col == s*3:\n",
    "                    return True\n",
    "            # 检查对角线\n",
    "            lr = rl = ''\n",
    "            for i in range(3):\n",
    "                lr += board[i][i]\n",
    "                rl += board[i][2-i]\n",
    "            if lr == s*3 or rl == s*3:\n",
    "                return True\n",
    "            \n",
    "            return False\n",
    "        \n",
    "        X, O = check('X'), check('O')\n",
    "        # 1.在已经决出胜负的情况下\n",
    "        if (X and not O and m['X']-m['O']==1) or (O and not X and m['O']==m['X']):\n",
    "            return True\n",
    "        # 2.没有决出胜负\n",
    "        diff = m['X'] - m['O']\n",
    "        if not (X or O) and 0 <= diff <= 1:\n",
    "            return True\n",
    "\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x, y = 0, 0\n",
    "        for i in board:\n",
    "            x += i.count('X')\n",
    "            y += i.count('O')\n",
    "        if y > x or x - y >= 2:\n",
    "            return False\n",
    "\n",
    "        ans = []\n",
    "        for i in range(3):\n",
    "            if board[i][0] == board[i][1] == board[i][2]:\n",
    "                ans.append(board[i][1])\n",
    "            if board[0][i] == board[1][i] == board[2][i]:\n",
    "                ans.append(board[1][i])\n",
    "        if board[0][0] == board[1][1] == board[2][2]:\n",
    "            ans.append(board[1][1])\n",
    "        if board[0][2] == board[1][1] == board[2][0]:\n",
    "            ans.append(board[1][1])\n",
    "\n",
    "        if len(ans) > 1:\n",
    "            return ans[0] == ans[1]\n",
    "        elif len(ans) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            if ans[0] == ' ':\n",
    "                return True\n",
    "            elif ans[0] == 'X':\n",
    "                return x - y == 1\n",
    "            elif ans[0] == 'O':\n",
    "                return x == y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[0][2] == p and board[1][1] == p and board[2][0] == p\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        # Count number of X and O\n",
    "        x_count = sum (row.count('X') for row in board)\n",
    "        o_count = sum(row.count('O') for row in board)\n",
    "\n",
    "        # Check if the num is valid\n",
    "        if o_count > x_count: return False\n",
    "        if x_count > o_count + 1: return False\n",
    "\n",
    "        def Win(player)->bool:\n",
    "            if board[0][0] == board[0][1] == board[0][2] == player:\n",
    "                return True\n",
    "            elif  board[1][0] == board[1][1] == board[1][2] == player:\n",
    "                return True\n",
    "            elif  board[2][0] == board[2][1] == board[2][2] == player:\n",
    "                return True\n",
    "            elif  board[0][0] == board[1][0] == board[2][0] == player:\n",
    "                return True\n",
    "            elif  board[0][1] == board[1][1] == board[2][1] == player:\n",
    "                return True\n",
    "            elif  board[0][2] == board[1][2] == board[2][2] == player:\n",
    "                return True\n",
    "            elif  board[0][0] == board[1][1] == board[2][2] == player:\n",
    "                return True\n",
    "            elif  board[0][2] == board[1][1] == board[2][0] == player:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        x_win = Win('X')\n",
    "        o_win = Win('O')\n",
    "\n",
    "        # 第二和第三条件\n",
    "        if x_win and o_win:  # 两个玩家不能同时赢\n",
    "            return False\n",
    "        if x_win and x_count == o_count:\n",
    "            return False\n",
    "        if o_win and x_count > o_count:\n",
    "            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        grid = []\n",
    "        on = 0\n",
    "        xn = 0\n",
    "        for i in range(len(board)):\n",
    "            grid.append([])\n",
    "            for j in range(len(board[i])):\n",
    "                if board[i][j] == \"X\":\n",
    "                    xn+=1\n",
    "                    grid[i].append('X')\n",
    "                elif board[i][j] == \"O\":\n",
    "                    on+=1\n",
    "                    grid[i].append('O')\n",
    "                else:\n",
    "                    grid[i].append(' ')\n",
    "        if on>xn:\n",
    "            return False\n",
    "        elif on<=xn and on+1 >= xn:\n",
    "            X = False\n",
    "            O = False\n",
    "            for i in range(3):\n",
    "                if grid[i][0]==grid[i][1] and  grid[i][2]==grid[i][1]:\n",
    "                    if grid[i][0] == 'X':\n",
    "                        X= True\n",
    "                    elif grid[i][0]=='O':\n",
    "                        O = True\n",
    "                if grid[0][i]==grid[1][i] and  grid[1][i]==grid[2][i]:\n",
    "                    if grid[0][i] == 'X':\n",
    "                        X= True\n",
    "                    elif grid[0][i]=='O':\n",
    "                        O = True\n",
    "            if grid[0][0] == grid[1][1] and grid[1][1] ==grid[2][2]:\n",
    "                if grid[0][0] == 'X':\n",
    "                    X= True\n",
    "                elif grid[0][0]=='O':\n",
    "                    O = True\n",
    "            if grid[2][0] == grid[1][1] and grid[1][1] ==grid[0][2]:\n",
    "                if grid[1][1] == 'X':\n",
    "                    X= True\n",
    "                elif grid[1][1]=='O':\n",
    "                    O = True\n",
    "            if X and O:\n",
    "                return False\n",
    "            elif X and xn == on:\n",
    "                return False\n",
    "            elif O and xn == on+1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        # n = len(board)\n",
    "        n = 3\n",
    "        x_num = self.counter(board, \"X\")\n",
    "        o_num = self.counter(board, \"O\")\n",
    "\n",
    "        # 顺序不对\n",
    "        if o_num > x_num or x_num-o_num>1: return False\n",
    "        # x赢 或 o赢\n",
    "        res1 = self.winer(board, n, \"X\")\n",
    "        res2 = self.winer(board, n, \"O\")\n",
    "        if x_num == o_num and res1 == \"X\": return False\n",
    "        if x_num > o_num and res2 == \"O\": return False\n",
    "\n",
    "        return True\n",
    "\n",
    "    # 统计各方棋子\n",
    "    def counter(self, board, x):\n",
    "        counts = 0 \n",
    "        for strs in board:\n",
    "            for s in strs:\n",
    "                if s == x:\n",
    "                    counts += 1 \n",
    "        return counts\n",
    "\n",
    "    # 判断谁赢得比赛\n",
    "    def winer(self, board, n, x):\n",
    "        slash1 = \"\"\n",
    "        slash2 = \"\"\n",
    "        for i in range(n):\n",
    "            column = \"\"\n",
    "            for j in range(n):\n",
    "                column += board[j][i]\n",
    "            if board[i] == x*n or column == x*n: return x\n",
    "            slash1 += board[i][i]\n",
    "            slash2 += board[i][n-i-1]\n",
    "        if slash1 == x*n or slash2 == x*n: return x\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        board_len = len(board)\n",
    "\n",
    "        def check(cha):\n",
    "            deal_cha = cha * board_len\n",
    "\n",
    "            found = any((\n",
    "                # 行判断：只需要判断board是否包含等于deal_cha的行\n",
    "                any(row == deal_cha for row in board),\n",
    "                # 列判断：使用zip把列表中的列取出，再判断\n",
    "                any(col == deal_cha for col in map(''.join, zip(*board))),\n",
    "                # 对角线判断\n",
    "                all(board[i][i] == cha for i in range(board_len)),\n",
    "                # 反对角线判断\n",
    "                all(board[i][board_len-i-1] == cha for i in range(board_len))\n",
    "            ))\n",
    "            return found\n",
    "        x_num = 0\n",
    "        o_num = 0\n",
    "        for row in board:\n",
    "            for i in row:\n",
    "                if i == \"X\":\n",
    "                    x_num += 1\n",
    "                elif i == \"O\":\n",
    "                    o_num += 1\n",
    "        if x_num - o_num == 1 and not check(\"O\"):\n",
    "            return True\n",
    "        if x_num == o_num and not check(\"X\"):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\r\n",
    "        x_cnt=0\r\n",
    "        o_cnt=0\r\n",
    "        for i in range(3):\r\n",
    "            for j in range(3):\r\n",
    "                if board[i][j]=='X':\r\n",
    "                    x_cnt+=1\r\n",
    "                elif board[i][j]=='O':\r\n",
    "                    o_cnt+=1\r\n",
    "        if o_cnt>x_cnt:\r\n",
    "            return False\r\n",
    "        if x_cnt-1>o_cnt:\r\n",
    "            return False\r\n",
    "        \r\n",
    "        def has_win(s:str):\r\n",
    "            pat=s*3\r\n",
    "            ret=0\r\n",
    "            for i in range(3):\r\n",
    "                if board[i]==pat:\r\n",
    "                    ret+=1\r\n",
    "                for j in range(3):\r\n",
    "                    if board[j][i]!=s:\r\n",
    "                        break\r\n",
    "                else:\r\n",
    "                    ret+=1\r\n",
    "            if board[0][0]==board[1][1]==board[2][2]==s:\r\n",
    "                ret+=1\r\n",
    "            if board[0][2]==board[1][1]==board[2][0]==s:\r\n",
    "                ret+=1\r\n",
    "            return ret\r\n",
    "\r\n",
    "        o_win=has_win('O')\r\n",
    "        x_win=has_win('X')\r\n",
    "        if o_win and x_win:\r\n",
    "            return False\r\n",
    "        if o_win and x_cnt!=o_cnt:\r\n",
    "            return False\r\n",
    "        if x_win and x_cnt-1!=o_cnt:\r\n",
    "            return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        n = len(board)\n",
    "        x_num = self.counter(board, \"X\")\n",
    "        o_num = self.counter(board, \"O\")\n",
    "\n",
    "        # 顺序不对\n",
    "        if o_num > x_num or x_num-o_num>1: return False\n",
    "        # x赢 或 o赢\n",
    "        res1 = self.winer(board, n, \"X\")\n",
    "        res2 = self.winer(board, n, \"O\")\n",
    "        if x_num == o_num and res1 == \"X\": return False\n",
    "        if x_num > o_num and res2 == \"O\": return False\n",
    "        if res1 != -1 and res2 != -1: return False # 输出赢家\n",
    "\n",
    "        return True\n",
    "\n",
    "    # 统计各方棋子\n",
    "    def counter(self, board, x):\n",
    "        counts = 0 \n",
    "        for strs in board:\n",
    "            for s in strs:\n",
    "                if s == x:\n",
    "                    counts += 1 \n",
    "        return counts\n",
    "\n",
    "    # 判断谁赢得比赛\n",
    "    def winer(self, board, n, x):\n",
    "        for i in range(n):\n",
    "            # 第i行的三个元素\n",
    "            row = board[i]\n",
    "            # 第i列的三个元素\n",
    "            column = \"\"\n",
    "            for j in range(n):\n",
    "                column += board[j][i]\n",
    "            if row == x*n or column == x*n: return x\n",
    "        slash1 = \"\"\n",
    "        slash2 = \"\"\n",
    "        for i in range(n):\n",
    "            slash1 += board[i][i]\n",
    "            slash2 += board[i][n-i-1]\n",
    "        if slash1 == x*n or slash2 == x*n: return x\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        board_len = len(board)\n",
    "\n",
    "        def check(cha):\n",
    "            deal_cha = cha * board_len\n",
    "\n",
    "            found = any((\n",
    "                # 行判断：只需要判断board是否包含等于deal_cha的行\n",
    "                any(row == deal_cha for row in board),\n",
    "                # 列判断：使用zip把列表中的列取出，再判断\n",
    "                any(col == deal_cha for col in map(''.join, zip(*board))),\n",
    "                # 对角线判断\n",
    "                all(board[i][i] == cha for i in range(board_len)),\n",
    "                # 反对角线判断\n",
    "                all(board[i][board_len-i-1] == cha for i in range(board_len))\n",
    "            ))\n",
    "            return found\n",
    "        x_num = 0\n",
    "        o_num = 0\n",
    "        for row in board:\n",
    "            for i in row:\n",
    "                if i == \"X\":\n",
    "                    x_num += 1\n",
    "                elif i == \"O\":\n",
    "                    o_num += 1\n",
    "        if x_num - o_num == 1 and not check(\"O\"):\n",
    "            return True\n",
    "        if x_num == o_num and not check(\"X\"):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        dp = [list(x) for x in board]\n",
    "        n = len(board)\n",
    "        x_count = sum([x.count('X') for x in dp])\n",
    "        o_count = sum([x.count('O') for x in dp])\n",
    "        if (x_count-o_count)>1 or (o_count>x_count):\n",
    "            return False\n",
    "        x_flag = 0\n",
    "        o_flag = 0\n",
    "        for i in range(n):\n",
    "            if all([x=='X' for x in dp[i]]) or all([x[i]=='X' for x in dp]):\n",
    "                x_flag = 1\n",
    "            if all([x=='O' for x in dp[i]]) or all([x[i]=='O' for x in dp]):\n",
    "                o_flag = 1\n",
    "        if all([dp[i][i]=='X' for i in range(n)]) or all([dp[i][n-i-1]=='X' for i in range(n)]):\n",
    "            x_flag = 1\n",
    "        if all([dp[i][i]=='O' for i in range(n)]) or all([dp[i][n-i-1]=='O' for i in range(n)]):\n",
    "            o_flag = 1\n",
    "        if (x_flag>0 and o_flag>0) or (x_flag>0 and x_count-o_count!=1) or (o_flag>0 and x_count!=o_count):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x_cnt, o_cnt = 0, 0\n",
    "        for row in board:\n",
    "            for i in row:\n",
    "                if i == 'X':\n",
    "                    x_cnt += 1\n",
    "                if i == 'O':\n",
    "                    o_cnt += 1 \n",
    "        \n",
    "        # X数量比O少 直接返回false\n",
    "        if x_cnt < o_cnt:\n",
    "            return False\n",
    "        elif x_cnt > o_cnt:\n",
    "            # X数量大于O数量超过1 直接返回false\n",
    "            if x_cnt > o_cnt + 1:\n",
    "                return False\n",
    "            # 若满足O已经赢了的几种情况 直接返回false\n",
    "            if board[0][0] == board[1][1] == board[2][2] == 'O' or board[0][2] == board[1][1] == board[2][0] == 'O': \n",
    "                return False\n",
    "            for i in range(3):\n",
    "                if board[i][0] == board[i][1] == board[i][2] == 'O': \n",
    "                    return False\n",
    "                if board[0][i] == board[1][i] == board[2][i] == 'O': \n",
    "                    return False\n",
    "        else:\n",
    "            # X数量等于O数量 此时找出满足X已经赢了的几种情况 直接返回false\n",
    "            if board[0][0] == board[1][1] == board[2][2] == 'X' or board[0][2] == board[1][1] == board[2][0] == 'X': \n",
    "                return False\n",
    "            for i in range(3):\n",
    "                if board[i][0] == board[i][1] == board[i][2] == 'X': \n",
    "                    return False\n",
    "                if board[0][i] == board[1][i] == board[2][i] == 'X': \n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        cntx = sum(sum(y == 'X' for y in x) for x in board)\n",
    "        cnto = sum(sum(y == 'O' for y in x) for x in board)\n",
    "        for x in zip(*board):\n",
    "            print(x)\n",
    "        wx = any(x == \"XXX\" for x in board) or any(\"\".join(x) == \"XXX\" for x in zip(*board)) \n",
    "        wx = wx or all(board[i][i] == 'X' for i in range(3))\n",
    "        wx = wx or all(board[i][2 - i] == 'X'for i in range(3))\n",
    "        wo = any(x == \"OOO\" for x in board) or any(\"\".join(x) == \"OOO\" for x in zip(*board))\n",
    "        wo = wo or all(board[i][i] == 'O' for i in range(3))\n",
    "        wo = wo or all(board[i][2 - i] == 'O'for i in range(3))\n",
    "        if wx and wo:\n",
    "            return False\n",
    "        if wx:\n",
    "            return cntx == cnto + 1\n",
    "        if wo:\n",
    "            return cntx == cnto\n",
    "        return cntx == cnto or cntx == cnto + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        a = 0\n",
    "        b = 0\n",
    "        arr = [[0]*3 for _ in range(3)]\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j]=='X':\n",
    "                    a+=1\n",
    "                    arr[i][j] = -1\n",
    "                elif board[i][j]=='O':\n",
    "                    b+=1\n",
    "                    arr[i][j] = 1\n",
    "        if a-b<0 or a-b>=2:\n",
    "            return False\n",
    "        T = False\n",
    "        F = False\n",
    "        #print(arr)\n",
    "        for i in range(3):\n",
    "            flag = 0\n",
    "            for j in range(3):\n",
    "                flag+=arr[i][j]\n",
    "            if flag==-3:\n",
    "                T = True\n",
    "            elif flag==3:\n",
    "                F = True\n",
    "        for i in range(3):\n",
    "            flag = 0\n",
    "            for j in range(3):\n",
    "                flag+=arr[j][i]\n",
    "            if flag==-3:\n",
    "                T = True\n",
    "            elif flag==3:\n",
    "                F = True\n",
    "        flag = 0\n",
    "        flag2 = 0\n",
    "        flag3 = 0\n",
    "        for i in range(3):            \n",
    "            flag+=arr[i][i]\n",
    "            flag2+=arr[i][2-i]\n",
    "            flag3+=arr[2-i][i]\n",
    "        if flag==-3:\n",
    "            T = True\n",
    "        elif flag==3:\n",
    "            F = True      \n",
    "        if flag2==-3:\n",
    "            T = True\n",
    "        elif flag2==3:\n",
    "            F = True\n",
    "        if flag3==-3:\n",
    "            T = True\n",
    "        elif flag3==3:\n",
    "            F = True\n",
    "        #print(T,F)\n",
    "        if T and F:\n",
    "            return False\n",
    "        #print(arr)\n",
    "        if T:\n",
    "            return a-b==1\n",
    "        if F:\n",
    "            return a==b\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "\n",
    "        x_cnt = 0\n",
    "        o_cnt = 0\n",
    "        for line in board:\n",
    "            for c in line:\n",
    "                if c == 'X':\n",
    "                    x_cnt += 1\n",
    "                elif c == 'O':\n",
    "                    o_cnt += 1\n",
    "        \n",
    "        if o_cnt > x_cnt or o_cnt < x_cnt - 1:\n",
    "            return False\n",
    "        \n",
    "        if x_cnt == o_cnt:\n",
    "            last = 'O'\n",
    "        else:\n",
    "            last = 'X'\n",
    "\n",
    "        pairs = [[(0,0), (1,1), (2,2)],[(0,2), (1,1), (2,0)]]\n",
    "\n",
    "        for i in range(3):\n",
    "            pairs.append([(i, 0), (i, 1), (i, 2)])\n",
    "            pairs.append([(0, i), (1, i), (2, i)])\n",
    "        \n",
    "        x_win = 0\n",
    "        o_win = 0\n",
    "\n",
    "        win_points = set()\n",
    "        for pair in pairs:\n",
    "            p1, p2, p3 = pair\n",
    "            x1, y1 = p1\n",
    "            x2, y2 = p2\n",
    "            x3, y3 = p3\n",
    "            if board[x1][y1] == board[x2][y2] == board[x3][y3]:\n",
    "                if board[x1][y1].strip():\n",
    "                    win_points.add(p1)\n",
    "                    win_points.add(p2)\n",
    "                    win_points.add(p3)\n",
    "                if board[x1][y1] == 'X':\n",
    "                    x_win += 1\n",
    "                if board[x1][y1] == 'O':\n",
    "                    o_win += 1\n",
    "        print(x_win)\n",
    "        print(o_win)\n",
    "        if x_win + o_win > 2:\n",
    "            return False\n",
    "        \n",
    "        if len(win_points) >= 6:\n",
    "            return False\n",
    "        \n",
    "        print(f'{x_win} {last}')\n",
    "        if (x_win == 1 and last == 'O') or (o_win == 1 and last == 'X'):\n",
    "            return False\n",
    "        \n",
    "        return True\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x_cnt = sum([sum([1 if ch == 'X' else 0 for ch in line]) for line in board ])\n",
    "        o_cnt = sum([sum([1 if ch == 'O' else 0 for ch in line]) for line in board ])\n",
    "\n",
    "        if abs(x_cnt - o_cnt) >= 2 or o_cnt > x_cnt: return False\n",
    "\n",
    "        def is_win(board: list[str], use: str) -> bool:\n",
    "            # 横竖\n",
    "            for i in range(3):\n",
    "                if (board[i][0] == use and board[i][1] == use and board[i][2] == use ) or \\\n",
    "                    (board[0][i] == use and board[1][i] == use and board[2][i] == use):\n",
    "                    return True\n",
    "           \n",
    "            # 斜着\n",
    "            return (board[0][0] == use and  board[1][1] == use and  board[2][2] == use) or \\\n",
    "                 (board[0][2] == use and  board[1][1] == use and  board[2][0] == use)\n",
    "\n",
    "       \n",
    "        return not (\n",
    "            x_cnt - 1 != o_cnt and is_win(board, 'X') or (x_cnt != o_cnt and is_win(board, 'O'))\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x = o = xw = ow = 0\n",
    "        for row in board:\n",
    "            s = set(row)\n",
    "            if len(s) == 1 and (t:=s.pop()) != ' ':\n",
    "                if t == 'X':\n",
    "                    xw += 1\n",
    "                else:\n",
    "                    ow += 1\n",
    "            for c in row:\n",
    "                if c == 'X':\n",
    "                    x += 1\n",
    "                elif c == 'O':\n",
    "                    o += 1\n",
    "        for c in range(len(board[0])):\n",
    "            t = board[0][c]\n",
    "            if t != \" \":\n",
    "                r = 0\n",
    "                while r < len(board) and board[r][c] == t:\n",
    "                    r += 1\n",
    "                if r == len(board):\n",
    "                    if t == \"X\":\n",
    "                        xw += 1\n",
    "                    else:\n",
    "                        ow += 1\n",
    "        mid = board[1][1]\n",
    "        if mid != \" \":\n",
    "            if board[0][0] == board[1][1] == board[2][2] or board[2][0] == board[1][1] == board[0][2]:\n",
    "                if mid == \"X\":\n",
    "                    xw += 1\n",
    "                else:\n",
    "                    ow += 1\n",
    "        if (x == o or x == o + 1) and not (xw and ow):\n",
    "            if xw:\n",
    "                return x == o + 1\n",
    "            elif ow:\n",
    "                return x == o\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        a, b = set(), set()\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 'O':\n",
    "                    b.add(i * 3 + j)\n",
    "                elif board[i][j] == 'X':\n",
    "                    a.add(i * 3 + j)\n",
    "        xc, oc = len(a), len(b)\n",
    "        if xc - oc > 1 or xc - oc < 0:\n",
    "            return False\n",
    "        \n",
    "        for i in a:\n",
    "            if i in b:\n",
    "                return False\n",
    "        ''' \n",
    "        遍历行，只能判断行连通\n",
    "        ''' \n",
    "        for i in range(3):\n",
    "            if xc - oc != 1 and i * 3 in a and i * 3 + 1 in a and i * 3 + 2 in a:\n",
    "                return False\n",
    "            if xc != oc and i * 3 in b and i * 3 + 1 in b and i * 3 + 2 in b:\n",
    "                return False\n",
    "        for j in range(3):\n",
    "            if xc - oc != 1 and j in a and j + 3 in a and j + 6 in a:\n",
    "                return False\n",
    "            if xc != oc and j in b and j + 3 in b and j + 6 in b:\n",
    "                return False\n",
    "\n",
    "        if xc - oc != 1 and ((0 in a and 4 in a and 8 in a) or (2 in a and 4 in a and 6 in a)):\n",
    "            return False\n",
    "        if xc != oc and ((0 in b and 4 in b and 8 in b) or (2 in b and 4 in b and 8 in b)):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x = o = xw = ow = 0\n",
    "        for row in board:\n",
    "            s = set(row)\n",
    "            if len(s) == 1 and (t:=s.pop()) != ' ':\n",
    "                if t == 'X':\n",
    "                    xw += 1\n",
    "                else:\n",
    "                    ow += 1\n",
    "            for c in row:\n",
    "                if c == 'X':\n",
    "                    x += 1\n",
    "                elif c == 'O':\n",
    "                    o += 1\n",
    "        for c in range(len(board[0])):\n",
    "            t = board[0][c]\n",
    "            if t != \" \":\n",
    "                r = 0\n",
    "                while r < len(board) and board[r][c] == t:\n",
    "                    r += 1\n",
    "                if r == len(board):\n",
    "                    if t == \"X\":\n",
    "                        xw += 1\n",
    "                    else:\n",
    "                        ow += 1\n",
    "        mid = board[1][1]\n",
    "        if mid != \" \":\n",
    "            if board[0][0] == board[1][1] == board[2][2] or board[2][0] == board[1][1] == board[0][2]:\n",
    "                if mid == \"X\":\n",
    "                    xw += 1\n",
    "                else:\n",
    "                    ow += 1\n",
    "        if (x == o or x == o + 1) and not (xw and ow):\n",
    "            if xw:\n",
    "                return x == o + 1\n",
    "            elif ow:\n",
    "                return x == o\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[0][2] == p and board[1][1] == p and board[2][0] == p\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x_count, o_count = 0, 0\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 'X':\n",
    "                    x_count += 1\n",
    "                elif board[i][j] == 'O':\n",
    "                    o_count += 1\n",
    "        \n",
    "        x_win = self.isWinner(board, 'X')\n",
    "        o_win = self.isWinner(board, 'O')\n",
    "\n",
    "        if x_count < o_count or x_count - o_count > 1:\n",
    "            return False\n",
    "\n",
    "        if o_win and (x_win or x_count != o_count):\n",
    "            return False\n",
    "        if x_win and x_count - o_count != 1:\n",
    "            return False\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    def isWinner(self, board, player):\n",
    "        for i in range(3):\n",
    "            if all([cell == player for cell in board[i]]):\n",
    "                return True\n",
    "            if all(board[j][i] == player for j in range(3)):\n",
    "                return True\n",
    "        \n",
    "        if all([board[i][i] == player for i in range(3)]) or \\\n",
    "        all([board[i][2-i] == player for i in range(3)]):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\r\n",
    "        x_cnt=0\r\n",
    "        o_cnt=0\r\n",
    "        for i in range(3):\r\n",
    "            for j in range(3):\r\n",
    "                if board[i][j]=='X':\r\n",
    "                    x_cnt+=1\r\n",
    "                elif board[i][j]=='O':\r\n",
    "                    o_cnt+=1\r\n",
    "        if x_cnt<o_cnt or x_cnt>o_cnt+1:\r\n",
    "            return False\r\n",
    "        \r\n",
    "        def has_win(s:str):\r\n",
    "            pat=s*3\r\n",
    "            for i in range(3):\r\n",
    "                if board[i]==pat:\r\n",
    "                    return True\r\n",
    "                for j in range(3):\r\n",
    "                    if board[j][i]!=s:\r\n",
    "                        break\r\n",
    "                else:\r\n",
    "                    return True\r\n",
    "            if board[0][0]==board[1][1]==board[2][2]==s:\r\n",
    "                return True\r\n",
    "            if board[0][2]==board[1][1]==board[2][0]==s:\r\n",
    "                return True\r\n",
    "            return False\r\n",
    "\r\n",
    "        o_win=has_win('O')\r\n",
    "        x_win=has_win('X')\r\n",
    "        if o_win and x_win:\r\n",
    "            return False\r\n",
    "        if o_win and x_cnt!=o_cnt:\r\n",
    "            return False\r\n",
    "        if x_win and x_cnt-1!=o_cnt:\r\n",
    "            return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        def win(winType: str) -> bool:\n",
    "            b0, b1, b2 = board[0], board[1], board[2]\n",
    "            # 行相等 / 列相等 / 对角线相等\n",
    "            return b0[0] == b0[1] == b0[2] == winType \\\n",
    "                or b1[0] == b1[1] == b1[2] == winType \\\n",
    "                or b2[0] == b2[1] == b2[2] == winType \\\n",
    "                or b0[0] == b1[0] == b2[0] == winType \\\n",
    "                or b0[1] == b1[1] == b2[1] == winType \\\n",
    "                or b0[2] == b1[2] == b2[2] == winType \\\n",
    "                or b0[0] == b1[1] == b2[2] == winType \\\n",
    "                or b0[2] == b1[1] == b2[0] == winType\n",
    "\n",
    "        cntO = sum(row.count('O') for row in board)\n",
    "        cntX = sum(row.count('X') for row in board)\n",
    "        # X 是先手\n",
    "        if cntO != cntX and cntO != cntX - 1:\n",
    "            return False\n",
    "        # X 赢\n",
    "        if win('X') and cntO != cntX - 1:\n",
    "            return False\n",
    "        # O 赢\n",
    "        if win('O') and cntO != cntX:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        n = 3\n",
    "        co_x = 0\n",
    "        co_o = 0\n",
    "        t_h_o = False\n",
    "        t_s_o = False\n",
    "        t_h_x = False\n",
    "        t_s_x = False\n",
    "        t_xie = True\n",
    "        t_w_xie = True\n",
    "        for i in range(3):\n",
    "            if board[i][0] ==board[i][1]==board[i][2] and board[i][0]=='X':\n",
    "                t_h_x = True\n",
    "            if board[i][0] ==board[i][1]==board[i][2] and board[i][0]=='O':\n",
    "                t_h_o = True\n",
    "            for j in range(3):\n",
    "                if board[0][j] == board[1][j] == board[2][j] and board[0][j]=='X':\n",
    "                    t_s_x = True\n",
    "                if board[0][j] == board[1][j] == board[2][j] and board[0][j]=='O':\n",
    "                    t_s_o = True\n",
    "                if board[i][j] == 'X':\n",
    "                    co_x+=1\n",
    "                elif board[i][j] == 'O':\n",
    "                    co_o+=1\n",
    "                if i == j and i >0 and board[i][i] !=board[i-1][i-1]:\n",
    "                    t_xie =False\n",
    "                if i == j and board[i][i] == ' ':\n",
    "                    t_xie = False\n",
    "                if j == n-i-1 and board[i][j] == ' ':\n",
    "                    t_w_xie = False\n",
    "                if j == n-i-1:\n",
    "                    print(board[i][j],board[i-1][j-1])\n",
    "                if j == n-i-1 and j < 2 and board[i][j] !=board[i-1][j+1]:\n",
    "                    \n",
    "                    t_w_xie =False\n",
    "        print(t_w_xie)\n",
    "        print(t_xie)\n",
    "        print(co_x,co_o)\n",
    "        if t_s_x and t_s_o:\n",
    "            print(111)\n",
    "            return False\n",
    "        if t_xie:\n",
    "            if board[1][1] =='X' and co_x == co_o:\n",
    "                print(6)\n",
    "                return False\n",
    "            if board[1][1] =='O' and co_x>co_o:\n",
    "                print(7)\n",
    "                return False \n",
    "        if t_w_xie:\n",
    "            if board[2][0] =='X' and co_x == co_o:\n",
    "                print(8)\n",
    "                return False\n",
    "            if board[2][0] =='O' and co_x>co_o:\n",
    "                print(9)\n",
    "                return False                  \n",
    "        if t_h_x and co_x == co_o:\n",
    "            print(10)\n",
    "            return False\n",
    "        if t_s_x and co_x == co_o:\n",
    "            print(1)\n",
    "            return False\n",
    "        if t_h_o and co_x>co_o:\n",
    "            print(2)\n",
    "            return False\n",
    "        # if t_s_o and co_x>co_o:\n",
    "        #     print(3)\n",
    "        #     return False\n",
    "        if co_x<co_o or co_x - co_o>=2:\n",
    "            print(5)\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "\n",
    "        x_cnt = 0\n",
    "        o_cnt = 0\n",
    "        for line in board:\n",
    "            for c in line:\n",
    "                if c == 'X':\n",
    "                    x_cnt += 1\n",
    "                elif c == 'O':\n",
    "                    o_cnt += 1\n",
    "        \n",
    "        if o_cnt > x_cnt or o_cnt < x_cnt - 1:\n",
    "            return False\n",
    "        \n",
    "        if x_cnt == o_cnt:\n",
    "            last = 'O'\n",
    "        else:\n",
    "            last = 'X'\n",
    "\n",
    "        pairs = [[(0,0), (1,1), (2,2)],[(0,2), (1,1), (2,0)]]\n",
    "\n",
    "        for i in range(3):\n",
    "            pairs.append([(i, 0), (i, 1), (i, 2)])\n",
    "            pairs.append([(0, i), (1, i), (2, i)])\n",
    "        \n",
    "        x_win = 0\n",
    "        o_win = 0\n",
    "\n",
    "        win_points = set()\n",
    "        for pair in pairs:\n",
    "            p1, p2, p3 = pair\n",
    "            x1, y1 = p1\n",
    "            x2, y2 = p2\n",
    "            x3, y3 = p3\n",
    "            if board[x1][y1] == board[x2][y2] == board[x3][y3]:\n",
    "                if board[x1][y1].strip():\n",
    "                    win_points.add(p1)\n",
    "                    win_points.add(p2)\n",
    "                    win_points.add(p3)\n",
    "                if board[x1][y1] == 'X':\n",
    "                    x_win += 1\n",
    "                if board[x1][y1] == 'O':\n",
    "                    o_win += 1\n",
    "        #print(x_win)\n",
    "        #print(o_win)\n",
    "        if x_win + o_win > 2:\n",
    "            return False\n",
    "        \n",
    "        if len(win_points) >= 6:\n",
    "            return False\n",
    "        \n",
    "        #print(f'{x_win} {last}')\n",
    "        if (x_win == 1 and last == 'O') or (o_win == 1 and last == 'X'):\n",
    "            return False\n",
    "        \n",
    "        return True\n",
    "                \n",
    "        # very ugly but answer is no good much"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        def isWin(board, ch):\n",
    "            if board[0][0] == board[0][1] == board[0][2] == ch:\n",
    "                return True\n",
    "            if board[1][0] == board[1][1] == board[1][2] == ch:\n",
    "                return True\n",
    "            if board[2][0] == board[2][1] == board[2][2] == ch:\n",
    "                return True\n",
    "            if board[0][0] == board[1][0] == board[2][0] == ch:\n",
    "                return True\n",
    "            if board[0][1] == board[1][1] == board[2][1] == ch:\n",
    "                return True\n",
    "            if board[0][2] == board[1][2] == board[2][2] == ch:\n",
    "                return True\n",
    "            if board[0][0] == board[1][1] == board[2][2] == ch:\n",
    "                return True\n",
    "            if board[0][2] == board[1][1] == board[2][0] == ch:\n",
    "                return True\n",
    "            return False\n",
    "        x_num = 0\n",
    "        o_num = 0\n",
    "        for st in board:\n",
    "            for ch in st:\n",
    "                if ch == 'X':\n",
    "                    x_num += 1\n",
    "                elif ch == 'O':\n",
    "                    o_num += 1\n",
    "        X_win = isWin(board, 'X')\n",
    "        O_win = isWin(board, 'O')\n",
    "        if X_win and O_win:\n",
    "            return False\n",
    "        elif X_win and not O_win and x_num - o_num == 1:\n",
    "            return True\n",
    "        elif O_win and not X_win and x_num == o_num:\n",
    "            return True\n",
    "        elif not X_win and not O_win and (x_num - o_num == 1 or x_num == o_num):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, board: List[str], char: str):\n",
    "        length = len(board)\n",
    "        # 检查横和竖\n",
    "        for i in range(length):\n",
    "            horizontal = board[i]\n",
    "            vertical = board[0][i] + board[1][i] + board[2][i]\n",
    "            if horizontal == char * length or vertical == char * length:\n",
    "                return True\n",
    "        # 检查交叉\n",
    "        if char * length == (board[0][0] + board[1][1] + board[2][2])\\\n",
    "                or char * length == (board[0][2] + board[1][1] + board[2][0]):\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x_count = 0\n",
    "        o_count = 0\n",
    "        for line in board:\n",
    "            for word in line:\n",
    "                if word == 'X':\n",
    "                    x_count += 1\n",
    "                elif word == 'O':\n",
    "                    o_count += 1\n",
    "\n",
    "        if x_count - o_count < 0 or x_count - o_count > 1:\n",
    "            return False\n",
    "\n",
    "        if self.check(board, 'X'):\n",
    "            return x_count - o_count == 1 and not self.check(board, 'O')\n",
    "        elif self.check(board, 'O'):\n",
    "            return x_count == o_count and not self.check(board, 'X')\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x = o = xw = ow = 0\n",
    "        for row in board:\n",
    "            s = set(row)\n",
    "            if len(s) == 1 and (t:=s.pop()) != ' ':\n",
    "                if t == 'X':\n",
    "                    xw += 1\n",
    "                else:\n",
    "                    ow += 1\n",
    "            for c in row:\n",
    "                if c == 'X':\n",
    "                    x += 1\n",
    "                elif c == 'O':\n",
    "                    o += 1\n",
    "        for c in range(len(board[0])):\n",
    "            t = board[0][c]\n",
    "            if t != \" \":\n",
    "                r = 0\n",
    "                while r < len(board) and board[r][c] == t:\n",
    "                    r += 1\n",
    "                if r == len(board):\n",
    "                    if t == \"X\":\n",
    "                        xw += 1\n",
    "                    else:\n",
    "                        ow += 1\n",
    "        mid = board[1][1]\n",
    "        if mid != \" \":\n",
    "            if board[0][0] == board[1][1] == board[2][2] or board[2][0] == board[1][1] == board[0][2]:\n",
    "                if mid == \"X\":\n",
    "                    xw += 1\n",
    "                else:\n",
    "                    ow += 1\n",
    "        if (x == o or x == o + 1) and not (xw and ow):\n",
    "            if xw:\n",
    "                return x == o + 1\n",
    "            elif ow:\n",
    "                return x == o\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        count, count_r, count_c, count_cr = [0, 0], [0, 0, 0], [0, 0, 0], [0, 0]\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 'X':\n",
    "                    count[0] += 1\n",
    "                    count_r[i] -= 1\n",
    "                    count_c[j] -= 1\n",
    "                    if i == j: count_cr[0] -= 1\n",
    "                    if i + j == 2: count_cr[1] -= 1\n",
    "                elif board[i][j] == 'O':\n",
    "                    count[1] += 1\n",
    "                    count_r[i] += 1\n",
    "                    count_c[j] += 1\n",
    "                    if i == j: count_cr[0] += 1\n",
    "                    if i + j == 2: count_cr[1] += 1\n",
    "\n",
    "        def cacl(n):\n",
    "            return sum(i == n for i in count_r) + sum(i == n for i in count_c) + sum(i == n for i in count_cr)\n",
    "\n",
    "        if count[0] == count[1] and cacl(-3) == 0 and cacl(3) <= 1:\n",
    "            return True\n",
    "        if count[0] - 1 == count[1] and cacl(3) == 0:\n",
    "            return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        tmp = board.copy()\n",
    "        color_list = []\n",
    "        count_dict = defaultdict(int)\n",
    "\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                count_dict[board[i][j]] += 1\n",
    "        if count_dict['O'] > count_dict['X'] or count_dict['X'] - count_dict['O'] > 1:\n",
    "            return False\n",
    "\n",
    "        for i in range(3):\n",
    "            color_list.append(\"\".join(board[j][i] for j in range(3)))\n",
    "\n",
    "        tmp += color_list\n",
    "        x1 = \"\".join([board[0][0], board[1][1], board[2][2]])\n",
    "        x2 = \"\".join([board[0][2], board[1][1], board[2][0]])\n",
    "        tmp.append(x1)\n",
    "        tmp.append(x2)\n",
    "\n",
    "        if 'XXX' in tmp and 'OOO' in tmp:\n",
    "            return False\n",
    "        elif 'XXX' in tmp:\n",
    "            return count_dict['X'] > count_dict['O']\n",
    "        elif 'OOO' in tmp:\n",
    "            return count_dict['X'] == count_dict['O']\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        count, count_r, count_c, count_cr = [0, 0], [0, 0, 0], [0, 0, 0], [0, 0]\n",
    "\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 'X':\n",
    "                    count[0] += 1\n",
    "                    count_r[i] -= 1\n",
    "                    count_c[j] -= 1\n",
    "                    if i == j: count_cr[0] -= 1\n",
    "                    if i + j == 2: count_cr[1] -= 1\n",
    "                elif board[i][j] == 'O':\n",
    "                    count[1] += 1\n",
    "                    count_r[i] += 1\n",
    "                    count_c[j] += 1\n",
    "                    if i == j: count_cr[0] += 1\n",
    "                    if i + j == 2: count_cr[1] += 1\n",
    "                \n",
    "        print(count)\n",
    "        print(count_c)\n",
    "        print(count_r)\n",
    "        print(count_cr)        \n",
    "\n",
    "\n",
    "        def cacl(n):\n",
    "            return sum(i == n for i in count_r) + sum(i == n for i in count_c) + sum(i == n for i in count_cr)\n",
    "\n",
    "\n",
    "\n",
    "        if count[0] == count[1] and cacl(-3) == 0 and cacl(3) <= 1:\n",
    "            return True\n",
    "        if count[0] - 1 == count[1] and cacl(3) == 0:\n",
    "            return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[0][2] == p and board[1][1] == p and board[2][0] == p\n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        oCount = sum(row.count('O') for row in board)\n",
    "        xCount = sum(row.count('X') for row in board)\n",
    "        return not (oCount != xCount and oCount != xCount - 1 or\n",
    "                    oCount != xCount and self.win(board, 'O') or\n",
    "                    oCount != xCount - 1 and self.win(board, 'X'))\n",
    "\n",
    "    def win(self, board: List[str], p: str) -> bool:\n",
    "        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or\n",
    "                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \\\n",
    "                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \\\n",
    "                   board[2][0] == p and board[1][1] == p and board[0][2] == p \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        def win(ch):\n",
    "            return any((board[i][0] == ch and board[i][1] == ch and board[i][2] == ch)\n",
    "                     or (board[0][i] == ch and board[1][i] == ch and board[2][i] == ch) for i in range(3)) \\\n",
    "                   or (board[0][0] ==  ch and board[1][1] == ch and board[2][2] == ch) \\\n",
    "                   or (board[0][2] == ch and board[1][1] == ch and board[2][0] == ch)\n",
    "\n",
    "        p1 = sum(row.count('X') for row in board)\n",
    "        p2 = sum(row.count('O') for row in board)\n",
    "        return not (p1 != p2 and p2 != p1 - 1\n",
    "                    or p1 != p2 and win(\"O\")\n",
    "                    or p2 != p1 - 1 and win(\"X\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        n = 3\n",
    "        co_x = 0\n",
    "        co_o = 0\n",
    "        t_h_o = False\n",
    "        t_s_o = False\n",
    "        t_h_x = False\n",
    "        t_s_x = False\n",
    "        t_xie = True\n",
    "        t_w_xie = True\n",
    "        for i in range(3):\n",
    "            if board[i][0] ==board[i][1]==board[i][2] and board[i][0]=='X':\n",
    "                t_h_x = True\n",
    "            if board[i][0] ==board[i][1]==board[i][2] and board[i][0]=='O':\n",
    "                t_h_o = True\n",
    "            for j in range(3):\n",
    "                if board[0][j] == board[1][j] == board[2][j] and board[0][j]=='X':\n",
    "                    t_s_x = True\n",
    "                if board[0][j] == board[1][j] == board[2][j] and board[0][j]=='O':\n",
    "                    t_s_o = True\n",
    "                if board[i][j] == 'X':\n",
    "                    co_x+=1\n",
    "                elif board[i][j] == 'O':\n",
    "                    co_o+=1\n",
    "                if i == j and i >0 and board[i][i] !=board[i-1][i-1]:\n",
    "                    t_xie =False\n",
    "                if i == j and board[i][i] == ' ':\n",
    "                    t_xie = False\n",
    "                if j == n-i-1 and board[i][j] == ' ':\n",
    "                    t_w_xie = False\n",
    "                if j == n-i-1 and j < 2 and board[i][j] !=board[i-1][j+1]:                \n",
    "                    t_w_xie =False\n",
    "        if t_s_x and t_s_o:\n",
    "            return False\n",
    "        if t_xie:\n",
    "            if board[1][1] =='X' and co_x == co_o:\n",
    "                return False\n",
    "            if board[1][1] =='O' and co_x>co_o:\n",
    "                return False \n",
    "        if t_w_xie:\n",
    "            if board[2][0] =='X' and co_x == co_o:\n",
    "                return False\n",
    "            if board[2][0] =='O' and co_x>co_o:\n",
    "                return False                  \n",
    "        if t_h_x and co_x == co_o:\n",
    "            return False\n",
    "        if t_s_x and co_x == co_o:\n",
    "            return False\n",
    "        if t_h_o and co_x>co_o:\n",
    "            return False\n",
    "        if co_x<co_o or co_x - co_o>=2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkTripleConnect(self, board):\n",
    "        bingo1, bingo2 = 0, 0\n",
    "        for i in range(3):\n",
    "            if board[i][0] == board[i][1] and board[i][1] == board[i][2]:\n",
    "                if board[i][0] == 'X':\n",
    "                    bingo1 += 1\n",
    "                if board[i][0] == 'O':\n",
    "                    bingo2 += 1\n",
    "            if board[0][i] == board[1][i] and board[1][i] == board[2][i]:\n",
    "                if board[0][i] == 'X':\n",
    "                    bingo1 += 1\n",
    "                if board[0][i] == 'O':\n",
    "                    bingo2 += 1\n",
    "        if board[0][0] == board[1][1] and board[1][1] == board[2][2]:\n",
    "            if board[0][0] == 'X':\n",
    "                bingo1 += 1\n",
    "            if board[0][0] == 'O':\n",
    "                bingo2 += 1\n",
    "        if board[2][0] == board[1][1] and board[1][1] == board[0][2]:\n",
    "            if board[2][0] == 'X':\n",
    "                bingo1 += 1\n",
    "            if board[2][0] == 'O':\n",
    "                bingo2 += 1\n",
    "        print(bingo1, bingo2)\n",
    "        if bingo1 + bingo2 > 2:\n",
    "            return False\n",
    "        if bingo1 == bingo2 and bingo1!=0:\n",
    "            return False\n",
    "        return True\n",
    "    def checkNum(self, board):\n",
    "        chN = True\n",
    "        nums1, nums2 = 0, 0\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 'X':\n",
    "                    nums1 += 1\n",
    "                if board[i][j] == 'O':\n",
    "                    nums2 += 1\n",
    "        if nums1 < nums2 or nums1-nums2>=2:\n",
    "            chN = False\n",
    "        \n",
    "        \n",
    "\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        chN = True\n",
    "        nums1, nums2 = 0, 0\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 'X':\n",
    "                    nums1 += 1\n",
    "                if board[i][j] == 'O':\n",
    "                    nums2 += 1\n",
    "        if nums1 < nums2 or nums1-nums2>=2:\n",
    "            chN = False\n",
    "        \n",
    "        chT = True\n",
    "        bingo1, bingo2 = 0, 0\n",
    "        for i in range(3):\n",
    "            if board[i][0] == board[i][1] and board[i][1] == board[i][2]:\n",
    "                if board[i][0] == 'X':\n",
    "                    bingo1 += 1\n",
    "                if board[i][0] == 'O':\n",
    "                    bingo2 += 1\n",
    "            if board[0][i] == board[1][i] and board[1][i] == board[2][i]:\n",
    "                if board[0][i] == 'X':\n",
    "                    bingo1 += 1\n",
    "                if board[0][i] == 'O':\n",
    "                    bingo2 += 1\n",
    "        if board[0][0] == board[1][1] and board[1][1] == board[2][2]:\n",
    "            if board[0][0] == 'X':\n",
    "                bingo1 += 1\n",
    "            if board[0][0] == 'O':\n",
    "                bingo2 += 1\n",
    "        if board[2][0] == board[1][1] and board[1][1] == board[0][2]:\n",
    "            if board[2][0] == 'X':\n",
    "                bingo1 += 1\n",
    "            if board[2][0] == 'O':\n",
    "                bingo2 += 1\n",
    "        \n",
    "        if bingo1 + bingo2 > 2:\n",
    "            chT = False\n",
    "        if bingo1 == bingo2 and bingo1!=0:\n",
    "            chT = False\n",
    "\n",
    "        if chN and chT:\n",
    "            if (bingo1 == 1 and nums1 == nums2) or (bingo2 == 1 and nums1 == nums2+1):\n",
    "                return False       \n",
    "            return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        x_count = 0\n",
    "        o_count = 0\n",
    "        for row in board:\n",
    "            for c in row:\n",
    "                if c == 'X':\n",
    "                    x_count += 1\n",
    "                elif c == 'O':\n",
    "                    o_count += 1\n",
    "        if x_count != o_count and x_count != o_count + 1:\n",
    "            return False\n",
    "        if self.check_win(board, 'X') and x_count != o_count + 1:\n",
    "            return False\n",
    "        if self.check_win(board, 'O') and x_count != o_count:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def check_win(self, board, param):\n",
    "        for i in range(3):\n",
    "            if board[i][0] == param and board[i][1] == param and board[i][2] == param:\n",
    "                return True\n",
    "            if board[0][i] == param and board[1][i] == param and board[2][i] == param:\n",
    "                return True\n",
    "        if board[0][0] == param and board[1][1] == param and board[2][2] == param:\n",
    "            return True\n",
    "        if board[0][2] == param and board[1][1] == param and board[2][0] == param:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        cnt_o = sum(row.count('O') for row in board)\n",
    "        cnt_x = sum(row.count('X') for row in board)\n",
    "        def check(c):\n",
    "            win = False\n",
    "            for row in board:\n",
    "                if row.count(c) == 3:\n",
    "                    win = True\n",
    "            for col in zip(*board):\n",
    "                if col.count(c) == 3:\n",
    "                    win = True\n",
    "                \n",
    "            i = j = 0\n",
    "            cnt = 0\n",
    "            while i < 3 and j < 3:\n",
    "                cnt += board[i][j] == c\n",
    "                i += 1\n",
    "                j += 1\n",
    "            if cnt == 3:\n",
    "                win = True\n",
    "            \n",
    "            i, j = 0, 2\n",
    "            cnt = 0\n",
    "            while i < 3 and j >= 0:\n",
    "                cnt += board[i][j] == c\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            if cnt == 3:\n",
    "                win = True\n",
    "            return win\n",
    "\n",
    "        if cnt_o > cnt_x:\n",
    "            return False\n",
    "        elif cnt_o == cnt_x:\n",
    "            # 只能是o赢\n",
    "            win_x, win_o = check('X'), check('O')\n",
    "            if win_x and win_o:\n",
    "                return False\n",
    "            elif not win_x and win_o:\n",
    "                return True\n",
    "            elif win_x and not win_o:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        elif cnt_x - cnt_o != 1:\n",
    "            return False\n",
    "        else:\n",
    "            # 只能是x赢\n",
    "            win_x, win_o = check('X'), check('O')\n",
    "            if win_x and win_o:\n",
    "                return False\n",
    "            elif not win_x and win_o:\n",
    "                return False\n",
    "            elif win_x and not win_o:\n",
    "                return True\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTicTacToe(self, board: List[str]) -> bool:\n",
    "        b = ''.join(board)\n",
    "        c2c = defaultdict(int)\n",
    "        for c in b:\n",
    "            c2c[c]+=1\n",
    "        if c2c['X'] == c2c['O'] or c2c['X'] == c2c['O']+1:\n",
    "            pass\n",
    "        else:\n",
    "            return False\n",
    "        # if c2c['X'] + c2c['O'] == 9:\n",
    "        #     return False\n",
    "        ind = [\n",
    "            [0,1,2],\n",
    "            [3,4,5],\n",
    "            [6,7,8],\n",
    "\n",
    "            [0,3,6],\n",
    "            [1,4,7],\n",
    "            [2,5,8],\n",
    "            [0,4,8],\n",
    "            [2,4,6],\n",
    "        ]\n",
    "        c3c = defaultdict(int)\n",
    "        for ind1 in ind:\n",
    "            x,y,z = ind1\n",
    "            st = b[x]+b[y]+b[z]\n",
    "            c3c[st]+=1\n",
    "        print(c3c)\n",
    "        if c3c['XXX'] >=1 and  c3c['OOO'] >=1:\n",
    "            return False\n",
    "        if c3c['XXX'] == 1 and c3c['OOO'] == 0:\n",
    "            if c2c['X'] == c2c['O'] +1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        if c3c['XXX'] == 0 and c3c['OOO'] == 1:\n",
    "            if c2c['X'] == c2c['O']:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "# XXX\n",
    "# oox\n",
    "# oox\n",
    "\n",
    "# XXX\n",
    "# XOO\n",
    "# OO \n",
    "\n",
    "# OXX\n",
    "# XOX\n",
    "# OXO\n",
    "\n",
    "# XOX\n",
    "# X O\n",
    "# X O"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
